Selepas peristiwa Sonic 3 & Knuckles, Sonic dan Tails mendeteksi bacaan tenaga yang kuat di Pulau Malaikat dan menaiki pesawat biplan mereka, Tornado, untuk menyiasat. Walau bagaimanapun, Dr. Eggman menghantar kumpulan elit EggRobos untuk mencapai isyarat sebelum Sonic dan Tails. EggRobos menggali sumber isyarat, sebuah batu permata ajaib yang dipanggil Phantom Ruby, sebaik Sonic dan Tails tiba. EggRobos mendapat kuasa baharu daripada ruby, menjadi Hard-Boiled Heavies, dan menghantar Sonic, Tails, dan penjaga pulau itu, Knuckles, melalui zon yang sebelum ini dilawati oleh ketiga-tiga mereka di mana mereka mengejar Eggman untuk menghalangnya daripada menggunakan kuasa ruby untuk kejahatan, bertembung dengan dia dan Heavies di sepanjang jalan.

Sonic dan kawan-kawannya mengetahui bahawa Eggman telah menggunakan kuasa Phantom Ruby untuk menguasai semula Little Planet dari Sonic CD. Mereka menaiki kubu robotik Eggman, mengalahkannya dan Heavies, dan melarikan diri tepat sebelum ia meletup. Jika ketujuh-tujuh Chaos Emeralds dikumpul semasa bermain sebagai Sonic, Phantom Ruby mengangkut dia dan Eggman ke dimensi lain. Di sana, pemimpin Heavies, Heavy King, mengkhianati Eggman dan mengambil batu delima, menjiwai dirinya dengan kuasa; Eggman menyerang Heavy untuk cuba menuntut semula. Sonic menggunakan Chaos Emeralds untuk menjadi Super Sonic dan melawan Eggman dan Heavy King secara berasingan untuk mengelakkan delima daripada menjadi milik mereka. Selepas pertempuran, Phantom Ruby bertindak balas dengan Zamrud, menafikan keadaan Super Sonic dan mencipta lubang cacing yang menelan dirinya dan Sonic, menjadikan Little Planet lenyap.